A key-value data store allows users to store and retrieve data in the form of key-value pairs. The “key” in a key-value pair may be referred to as an index (e.g., a number, string, etc.) that uniquely identifies its paired value. The “value” in a key-value pair can be an arbitrary block of data and may comprise any type of data object or collection of data objects. A typical key-value store may expose three operations to users: PUT, GET, and DELETE. The PUT operation may be invoked to store one or more specified key-value pairs in the key-value store. The GET operation may be used to retrieve the values for one or more specified keys from the key-value store. The DELETE operation may delete key-value pairs identified by one or more specified keys from the key-value store.
Some key-value stores may be distributed. A distributed key-value storage system allows users to invoke key-value operations such as PUT, GET, and DELETE, on any one of a set of distinct computers (either physical or virtual) referred to as “nodes.” A distributed key-value store may be implemented in a data center having several nodes. Some of the nodes may have a copy of the key-value store, thus allowing for high speed access. A consensus algorithm may be used to coordinate a reliable replication of a key-value store among several nodes. This kind of distributed key-value store conventionally assumes the nodes are connected by high-throughput, low-latency connections, which is typically the case in a data center.
However, in a distributed configuration over a wide area network, portions of the key-value store may be stored in nodes outside of the data center. The assumption of a high-throughput, low-latency connections with such nodes is not guaranteed. Nodes outside of a data center may be geographically separated (i.e., large distances) from the data center, and so communications may occur over lower cost connections, which can mean lower capacity and/or lower reliability (even unguaranteed) connections.